package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * 使用HashMap
 *
 * @author fy
 * @date 2022/4/18 21:29
 */
public class Solution211 {

    class WordDictionary {

        private class Node {
            private boolean isWord;
            private Map<Character, Node> next;

            private Node() {
                this(false);
            }

            private Node(boolean isWord) {
                this.isWord = isWord;
                this.next = new HashMap<>();
            }
        }

        private Node root;

        public WordDictionary() {
            root = new Node();
        }

        public void addWord(String word) {
            Node node = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (node.next.get(ch) == null) {
                    node.next.put(ch, new Node());
                }
                node = node.next.get(ch);
            }
            node.isWord = true;
        }

        public boolean search(String word) {
            return dfsSearch(word, 0, root);
        }

        private boolean dfsSearch(String word, int index, Node node) {
            if (index == word.length()) {
                return node.isWord;
            }
            char ch = word.charAt(index);
            if (ch != '.') {
                if (node.next.get(ch) == null) {
                    return false;
                }
                return dfsSearch(word, index + 1, node.next.get(ch));
            } else {
                for (char key : node.next.keySet()) {
                    if (dfsSearch(word, index + 1, node.next.get(key))) {
                        return true;
                    }
                }
                return false;
            }
        }
    }

}
